The invention relates generally to data compression. More specifically, the invention relates to encoding/decoding data for use in communications systems.
One design factor in communication systems is the scheme of encoding used to transmit data. One such scheme, popular in serial communication lines such as T1 is referred to as Non Return to Zero Inverted (NRZI) encoding. In NRZI, the last transmitted bit is fed back or stored to determine the outcome of the next bit encoded. FIG. 1 shows a traditional NRZI encoding engine 100 that encodes an input bitstream 105 into an output bitstream 110. The last transmitted bit is fed back into the encoding engine 100 to determine the next bit in output bitstream 110. The logic for determining the content of output bitstream 110 is as follows. If the current bit of input bitstream 105 is a zero, then the current output bit is the opposite of the last transmitted bit. If however the current input bit is one, then the output bit is the same as the last transmitted bit. For instance, consider the following input bitstream xe2x80x9c0110010111010xe2x80x9d (from left to right) and that the start is a low state or a zero. In this case the output bitstream would be xe2x80x9c1110110000110xe2x80x9d. NRZI encoding is inherently serial in nature, since the last transmitted bit determines how the current input bit should be handled in order to encode that current input bit. Thus, for a unit of data such as an 8-bit byte to be NRZI encoded, it must be processed bit-by-bit in a serial fashion. This impacts the speed and efficiency of the communications system in handling data through its nodes. If bytes or other units of data could be encoded and decoded through NRZI but without resorting to serializing of the data and then re-assembly back into bytes, system efficiency can be increased.
Another technique called Zero Insertion is used to prevent a long string of ones a phenomenon known as flag sequence duplication. In SDLC (Synchronous Data Link Control), a flag sequence known as the xe2x80x9c7Exe2x80x9d flag separates frames of data. The binary equivalent of the 7E flag would be 01111110, and thus has a string of 6 consecutive ones. If such a string occurs in the data stream itself (between real 7E flags), the decoding may confuse it for a flag indicating the start of another frame. To avoid this confusion, whenever a series of five 1s is encountered, a zero is inserted into the data stream. As with the NRZI encoding process, this too is inherently serial, in that the number of consecutive ones must be counted as they occur in the data stream. When decoded, these zeroes are removed, also in the same serial manner. As a result, even if NRZI itself were not serial, zero insertion and removal would still remain a strictly serial operation, once again adversely impacting the speed of the communications system.
What is disclosed is a method comprising forming an address for non-return-to zero inverted (NRZI) encoding of a current input data byte, and accessing in a look-up table an NRZI output value pointed to by the address, the NRZI output value the equivalent of having performed NRZI encoding upon the current input data byte.